This course will study various techniques for designing and analyzing algorithms. We will mainly focus on problems for which the exact algorithm is not known or not efficient enough and problems with resource constraints. Besides designing efficient algorithms, proving the performance guarantees is also a main topic of this course. Some topics that we will cover are as follows:

Approximation Algorithms: Algorithms that find near-optimal solutions with provable performance guarantees in polynomial time. This course will mainly focus on approximation algorithms for NP-hard problems.

Randomized Algorithms: Algorithms that use random numbers. We will focus on algorithms with provable success probabilities and good expected solution quality.

Streaming Algorithms: Algorithms that solve problems on massive datasets. In this type of problem, usually, the algorithm is only allowed to read the data once and use no more than a constant or poly-logarithmic amount of space.

Online Algorithm: The input to the problem is not known in advance and arrives over time. An online algorithm must decide how to process a specific input before seeing future inputs. The goal is to perform as well as an algorithm that knows all inputs beforehand.

We will cover algorithm design techniques such as hashing, sampling, and linear programming.